package com.example.demo.Calss16_graph;

import java.util.ArrayList;

/**
 * @program: java_base
 * @description: 树结构 拓扑遍历
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/02 13:27
 */
// OJ链接：https://www.lintcode.com/problem/topological-sorting
public class Code03_TopologicalOrderBFSDemo {

    /**
     * 遍历图结构，从节点in指向为0的为首，入队，依次排列输出
     * 基本要求：
     *      1.在图中找到所有入度为0的点输出
     *      2.把所有入度为零的点在图中删除，继续找到入度为0的点输出，周而复始
     *      3.图的所有点都被删除后，依次输出的顺序就是拓扑排序
     * 要求：有向图且其中没有环
     * 应用：事件排序 / 编译顺序
     */

    /////

    // 提交下面的
    public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {


        return null;
    }

    /**
     * 这个类似于 表形式
     * a --> b ,c d, e, f
     * c --> b ,c d,
     */
    // 不要提交这个类
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }
}
